#include <stdio.h>
#include <stdlib.h>

#define NAMESIZE 32

struct score
{
	int id;
	char name[NAMESIZE];
	int math;
	int chinese;
};
struct node
{
	struct score data;
	struct node *left;
	struct node *right;
};

void print_s(struct score *current)
{
	printf("%d %s %d %d\n", current->id, current->name, current->chinese, current->math);
}

int insert(struct node **root, struct score *data);
struct score *find(struct node *root, int id);
void draw(struct node *root);
void draw_(struct node *root, int level);

int main(void)
{
	int arr[] = {1, 2, 3, 7, 6, 5, 9, 8, 4}; //小数往左，大数往右
	struct node *tree = NULL;
	struct score tmp;
	//不需要头结点
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		tmp.id = arr[i];
		snprintf(tmp.name, NAMESIZE, "stu%d", arr[i]);
		tmp.math = rand() % 100;
		tmp.chinese = rand() % 100;
		insert(&tree, &tmp); //由于不带头结点，这棵树的起始位置会变化，所以传入tree的地址
	}
	int tmpid = 12;
	struct score *datap = NULL;
	datap = find(tree, tmpid);
	if (datap == NULL)
		printf("Can not find id = %d\n", tmpid);
	else
		print_s(datap);
	printf("\n\n");
	draw(tree);
	return 0;
}

int insert(struct node **root, struct score *data) //二级指针
{
	struct node *tmp;
	if (*root == NULL) //树为空
	{
		tmp = malloc(sizeof(struct node));
		if (tmp == NULL)
			return -1;
		tmp->data = *data;
		tmp->left = NULL;
		tmp->right = NULL;
		*root = tmp;
		return 0;
	}
	if (data->id <= (*root)->data.id)
		return insert(&(*root)->left, data);
	else
		return insert(&(*root)->right, data);
}
struct score *find(struct node *root, int id)
{
	if (root == NULL)
		return NULL;
	if (id == root->data.id)
		return &root->data;
	else if (id < root->data.id)
		return find(root->left, id);
	else
		find(root->right, id);
}

void draw_(struct node *root, int level)
{
	if (root == NULL)
		return;
	draw_(root->right, level + 1);
	for (int i = 0; i < level; i++)
		printf("	");
	printf("%d\n", root->data.id);
	// print_s(&root->data);
	draw_(root->left, level + 1);
}
void draw(struct node *root)
{
	draw_(root, 0);
}
get_num(struct node *root)
{
	if (root == NULL)
		return 0;
	return get_num(root->left) + 1 + get_num(root->right);
}
struct node *find_min(struct node *root)
{
	if (root->left == NULL)
		return root;
	return find_min(root->left);
}
static void turn_left(struct node **root)
{
	struct node *current = *root;
	*root = current->right;
	current->right = NULL;
	find_min(*root)->left = current;
}
static struct node *find_max(struct node *root)
{
	if (root->right == NULL)
		return root;
	find_max(root->right);
}
void turn_right(struct node **root)
{
	struct node *current = *root;
	*root = current->left;
	current->left = NULL;
	find_max(*root)->right = current;
}
void balance(struct node **root) //平衡时树根要变化
{
	if (*root == NULL)
		return;
	while (1)
	{
		int sub = get_num((*root)->left) - get_num((*root)->right);
		if (sub >= -1 && sub <= 1) //左右差值小于等于1
			break;
		if (sub < -1)
			turn_left(root); //左旋
		else
			turn_right(root); //右旋
	}
	balance(&(*root)->left);
	balance(&(*root)->right);
}